我们常用树这种数据结构，原因是树结合了有序数组和链表的优点，这使得在树中查找数据项的速度和在有序数组中查找一样快，而且插入和删除数据项的速度也同链表一样。下面我们具体分析一下有序数组和链表的缺点，树是怎样使两者的优点集中在一起的。

那么是否有一种数据结构，既能像链表那样进行快速的插入删除数据，又能像有序数组那样快速查找呢？树就实现了这一点。

这里的树和生活中的树类似，具有根、树枝、叶子等结构。简单来说，树由边连接的节点构成。在数据结构中，树的定义如下： 树（Tree）是n（n>=0）个节点的有限集。当n=0时称为空树。在任意一个非空树中都有如下特点： 1. 有且仅有一个特点的节点，称为根。 2. 当n>1时，其余节点可分为m（m>0）个互不相交的有限集，每一个集合本身又是一个树，称为根的子树。 下图展示了一个树的例子，在图中我们使用圆来代表节点，连接圆的直线代表边。 这里介绍一下与树相关的术语：

二叉树（binary tree）是树的一种特殊形式。这种树的每个节点最多只能有两个子节点。（注意是最多，可以是一个，也可以没有子节点） 二叉树节点的两个子节点（孩子节点），一个被称为左孩子（left child），一个被称为右孩子（right child）。这两个子节点的顺序是固定的，不能颠倒或混淆。 二叉树本身还存在两种特殊的形式，一个是满二叉树、一个是完全二叉树。

满二叉树： 一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一个层级上，那么这个树就是满二叉树。简单说，满二叉树的每一个分支都是满的。 下图就是一个满二叉树。

完全二叉树： 对一个又n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。 下图就是一个完全二叉树，二叉树编号1-4的4个节点，和前面满二叉树编号从1到7的位置对应，因此这是一个完全二叉树。 可以这样理解，在满二叉树中去掉一些子节点及其下面连接的子节点就得到了完全二叉树。

总结： 满二叉树要求所有分支都是满的；而完全二叉树只需保证最后一个节点之前开始的节点都齐全即可。

下面主要介绍二叉树的存储结构和应用。

二叉树是一种”逻辑结构“，可以通过多种物理结构来表达。这里以链式存储结构和数组这两种物理结构为例来思考二叉树的存储结构。

这是二叉树最直观的存储方式。链表是“一对一”的存储方式，没一个链表节点拥有data变量和一个指向下一节点的next指针。 而再二叉树中，我们需要又两个指针来分别指向一个节点的左孩子和右孩子节点。每一个结点由下图的三部分构成：

在使用数组存储时，会按照一定的层级顺序把各个结点都放置到数组中对应的位置上。如果某一个结点的左孩子/右孩子不存在，数组上也要把这一位空出来。 为了方便的在数组中定位二叉树的孩子节点和父节点，这里我们按下面的规则来进行对应。 如果一个父节点的下标是parent，那么它的左孩子节点的下标是2*parent+1；右孩子节点的下标是2*parent+2。反之，一个左孩子节点的下标是left，则他的父节点下标就是(left-1)/2。 一个例子如下图，以节点7为例，它的父节点是5，是5的右孩子，而5存在数组的4号位置，因此节点7的位置是4*2+2=10。

从上面的图例中我们不难发现，对于一个稀疏的二叉树来说，采用数组来表示是很浪费空间的。而完全二叉树比较适合用这种方式来存储（如二叉堆）。

二叉树的树形结构十分适合作索引。而二叉查找树（binary search tree）的主要作用就是进行查找。 一个标准的二叉查找树如下图所示，二叉查找树在普通二叉树的基础上增加了下面三个条件：

这样的要求能大大方便我们进行查找。 下面以查找值为4的节点为例，来看一下如何完成查找操作。

总结：对于一个节点分布相对均衡的二叉查找树来说，如节点总数为n，那么搜索节点的时间复杂度为O(nlogn)。这种依靠比较大小来逐步查找的方式，类似二分查找。

在二叉查找树中我们要求左子树小于父节点，右子树大于父节点，因此保证了二叉树具有一定范围内的有序。二叉查找树也称二叉排序树（binary sort tree）。新插入二叉排序树的节点也要遵守这个规则来插入。

例如现在要插入一个节点5，先和根比较，发现5根节点->右子树。(即根节点在中间) 还是用同样的例子来说明中序遍历的过程。

首先访问根节点的左孩子，如果这个左孩子还有左孩子就继续找下去，直到不再有左孩子为止。找到没有左孩子的节点是4，输出。

此时向上找这个节点的父节点2，输出。

找到这个节点的右孩子5，输出。

输出根节点1。

根节点的右孩子3没有左节点，因此输出它自己。

最后输出右节点6。

输出顺序：左子树->右子树->根节点。（根节点最后输出） 还是以下图来说明后序遍历的过程。

对二叉树进行深度优先遍历可以采用递归和非递归两种方式，递归比较简单但是理解上可能不太容易。首先看下面对二叉树类的构建。

然后我们首先要对二叉树进行构造，构造一个二叉树然后才能对它进行遍历，我们构建下图这样一个二叉树，使用前序的顺序输入如下数据：

我们先使用代码简单的递归来实现遍历，完整代码如下：

测试运行结果如下：

当然也可以用非递归方式来实现遍历，这里借助栈来实现同样的操作。 下面以前序遍历为例，说明具体实现过程。

广度优先遍历和在一个方向上”直接到底“的深度优先遍历相反，它是先在各个方向上各走出一步，再在各个方向上走出第2、3步…直到各个方向全部走完。 下面以二叉树的层序遍历为例说明广度优先遍历的特点。 层序遍历，是指二叉树按照从根节点到叶子节点的层次关系，一层层地横向遍历各个节点。 我们知道，二叉树同一层次的节点之间是没有任何关联的，如何实现层序遍历呢？我们使用数据结构队列。以下图为例，一个二叉树的层序遍历实现如下：

根节点1插入队列。

节点1出队，输出节点1，并得到节点1的左孩子节点2和右孩子节点3。让节点2、3入队。

节点2出队，输出节点2，并得到节点2的左孩子节点4、右孩子节点5。让节点4、5入队。

节点3出队，输出节点3，并得到节点3的右孩子节点6，让节点6入队。

节点4出队，输出节点4，因为4没有子节点，故没有新节点入队。

节点5出队，输出节点5，因为节点5也没有子节点，没有新节点入队。

节点6出队，输出节点6，因为节点6没有子节点，所以没有新入队节点。此时栈为空，所有节点遍历结束。

二叉堆可以通过自身调整，让最大或最小的元素移动到顶点。 二叉堆是实现堆排序和优先队列的基础。

二叉堆本质上是一种完全二叉树，它分为以下两个类型。

最大堆。 任何一个父节点的值都大于或者等于它左、右孩子节点的值。下图就是一个最大堆。

最小堆。 任何一个父节点的值，都小于或等于它左、右孩子节点的值。 下图是一个最小堆。

二叉堆的根节点叫做堆顶。最大堆和最小堆的特点决定了：最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶是整个堆中的最小元素。

对于二叉堆有如下几种操作。

这三种操作都基于堆的自我调整。堆的自我调整就是把一个不符合堆的性质的完全二叉树，调整成一个堆。 下面以最小堆的构建为例，看一个完全二叉树是如何自我调整的。

在二叉堆中，新插入的位置都是完全二叉树的最后一个位置。例如现在往下图所示的二叉树中插入一个节点0。 此时新节点的父节点5比0大，需要将新节点”上浮“，和父节点进行位置交换。 继续把新节点0和它的父节点3作比较，0 int []array =new int[]{1,3,2,6,5,7,8,9,10,0}; upMove(array); System.out.println(Arrays.toString(array)); array=new int[]{7,1,3,10,5,2,8,9,6}; buildHeap(array); System.out.println(Arrays.toString(array)); } /* 节点"上浮"移动 【用于在二叉堆中插入一个新节点时】 @param array 待调整的heap */ public static void upMove(int []array){ int childIndex=array.length-1; int parentIndex=(childIndex-1)/2; int tmp=array[childIndex];//保存插入的叶子节点值，赋值用 while (childIndex>0 &&tmp int childIndex=2*parentIndex+1; int tmp=array[parentIndex];//保存父节点值，赋值用 while (childIndex childIndex++; } //如果父节点比子节点值小，完成下沉，跳出 if(tmp //从【最后一个非叶子节点】开始，依次做“下沉”调整 for(int i=(array.length-2)/2; i>=0; i--){ downMove(array,i,array.length); } } }

测试运行结果如下：

我们回顾一下队列的特点，队列是一种遵循先进先出（FIFO）的数据结构，在入队时，新元素将被置于队尾：

在出队时，只有队头元素能被移出： 那么优先队列和普通队列之间有何区别呢？ 优先队列不再遵循FIFO规则，它的优先级规则如下：

用下图来说明这个规则，这是一个最大优先队列，最大元素是8，尽管8并不是队首元素，但出队的元素却是8。

通过前面的介绍，最大堆和最小堆来实现最大优先队列和最小优先队列是最佳的选择。每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。 下面以最大优先队列为例，说明入队、出队操作的过程。

让原堆顶节点10出队。

把最后一个节点1直接替换到堆顶，顶替出队的原堆顶。

使节点1“下沉”到合适位置，最终节点9称为堆顶。

总结：二叉堆节点“上浮”、“下沉”的时间复杂度都是O(logn)，所以优先队列入队和出队的时间复杂度也是O(logn)。

拓展：可以使用JDK提供的java.util.PriorityQueue直接完成优先队列的实现。关于PriorityQueue的介绍如下： Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。 优先队列的作用是能保证每次取出的元素都是队列中权值最小的（Java的优先队列每次取最小元素，C++的优先队列每次取最大元素）。元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器来定义。

在如下代码中，我们构建了一个最小优先队列，即每次都是最小的元素先出队。

测试运行结果如下： 第一次2最小，所以2出队；然后3是最小元素，所以第二次3出队。